//public class Main {
//    // 0-1 背包问题的求解函数
//    public static int bag(int W, int[] weight, int[] val) {
//        int n = weight.length;             // 物品数量
//        int[] dp = new int[W + 1];         // dp[j] 表示容量为 j 时的最大价值，初始化为 0
//        // 遍历每个物品
//        for (int i = 0; i < n; i++) {
//            // 倒序遍历容量，确保每件物品只被使用一次（0-1背包）
//            for (int j = W; j >= weight[i]; j--) {
//                // 状态转移：不选 或 选当前物品，取两者最大值
//                dp[j] = Math.max(dp[j], dp[j - weight[i]] + val[i]);
//            }
//        }
//        // 返回背包容量为 W 时的最大总价值
//        return dp[W];
//    }
//    // 主函数，测试用例
//    public static void main(String[] args) {
//        int[] weight = {2, 1, 3};  // 物品重量
//        int[] value = {4, 2, 3};   // 物品价值
//        int W = 4;                 // 背包容量
//        // 输出最大价值
//        System.out.println("最大价值为：" + bag(W, weight, value));
//    }
//}




//public class Main {
//    // 完全背包问题
//    public static int CompleteBag(int W, int[] weight, int[] val) {
//        int n = weight.length;             // 物品数量
//        int[] dp = new int[W + 1];         // dp[j] 表示容量为 j 时的最大价值，初始为 0
//        // 遍历每个物品（可以无限次使用）
//        for (int i = 0; i < n; i++) {
//            // 正序遍历容量，允许一个物品使用多次（完全背包特征）
//            for (int j = weight[i]; j <= W; j++) {
//                // 状态转移方程：选与不选当前物品，取最大值
//                dp[j] = Math.max(dp[j], dp[j - weight[i]] + val[i]);
//            }
//        }
//        // 返回背包容量为 W 时的最大总价值
//        return dp[W];
//    }
//    // 主函数，测试样例
//    public static void main(String[] args) {
//        int[] weight = {2, 1, 3};  // 物品重量
//        int[] val = {4, 2, 3};     // 物品价值
//        int W = 4;                 // 背包总容量
//
//        // 输出背包能获得的最大价值
//        System.out.println("最大价值为：" + CompleteBag(W, weight, val));
//    }
//}


public class Main {
    // 多重背包问题
    public static int MultiplyBag(int W, int[] weight, int[] val, int[] count) {
        int n = weight.length;             // 物品数量
        int[] dp = new int[W + 1];         // dp[j] 表示容量为 j 时的最大价值，初始为 0
        // 遍历每个物品
        for (int i = 0; i < n; i++) {
            int num = count[i];  // 获取当前物品的最大数量
            // 使用二进制优化来将物品拆分成多个 0-1 背包问题的物品
            for (int k = 1; num > 0; k <<= 1) {
                int use = Math.min(k, num);    // 选取当前物品的数量
                int w = use * weight[i];       // 当前选用物品的总重量
                int v = use * val[i];          // 当前选用物品的总价值

                // 内层倒序遍历背包容量，确保每个物品只能选用一次
                for (int j = W; j >= w; j--) {
                    dp[j] = Math.max(dp[j], dp[j - w] + v);  // 状态转移
                }

                num -= use;  // 剩余可以使用的物品数量
            }
        }
        // 返回背包容量为 W 时的最大总价值
        return dp[W];
    }
    // 主函数，测试样例
    public static void main(String[] args) {
        int[] weight = {2, 1, 3};     // 物品的重量数组
        int[] value = {4, 2, 3};      // 物品的价值数组
        int[] count = {2, 3, 1};      // 每种物品的数量限制数组
        int W = 4;                    // 背包容量

        // 输出背包能获得的最大价值
        System.out.println("最大价值为：" + MultiplyBag(W, weight, value, count));
    }
}

